home *** CD-ROM | disk | FTP | other *** search
/ MacHack 1997 / MacHack 1997.toast / Hacks / Hacks ’97 / Warrior’s Progress / source code / Source / Libraries / Heap / Heap.cp next >
Encoding:
Text File  |  1997-06-28  |  5.0 KB  |  267 lines  |  [TEXT/CWIE]

  1. // Heap.cp
  2.  
  3. #ifndef Heap_h
  4. #include "Heap.h"
  5. #endif
  6. #ifndef HeapLink_h
  7. #include "HeapLink.h"
  8. #endif
  9. #ifndef Swap_h
  10. #include "Swap.h"
  11. #endif
  12.  
  13. template< class Element >
  14. Heap< Element >::Heap( Comparator compare )
  15.   : nodeCount( 0 ),
  16.      top( 0 ),
  17.      below( compare )
  18.   {
  19.     Assert( compare != 0 );
  20.   }
  21.  
  22. template< class Element >
  23. Heap< Element >::~Heap()
  24.   {
  25.     Assert( nodeCount == 0 );
  26.     Assert( top == 0 );
  27.   }
  28.  
  29. template< class Element >
  30. HeapLink<Element>& Heap< Element >::Pop()
  31.   {
  32.     HeapLink<Element>& result = Top();
  33.     Remove( result );
  34.     return result;
  35.   }
  36.  
  37. template< class Element >
  38. void Heap< Element >::Add( LinkType& toAdd )
  39.   {
  40.     Assert( toAdd.heap == 0 );
  41.     toAdd.heap = this;
  42.     
  43.     Assert( toAdd.children[0] == 0 );
  44.     Assert( toAdd.children[1] == 0 );
  45.     
  46.     toAdd.path = ++nodeCount;
  47.     
  48.     LinkType **subHeap = ⊤
  49.     LinkType *carrying = &toAdd;
  50.     SinkNode( subHeap, carrying );
  51.  
  52.     Assert( *subHeap == 0 );
  53.     Assert( carrying->path == nodeCount );
  54.     Assert( carrying->children[0] == 0 );
  55.     Assert( carrying->children[1] == 0 );
  56.     
  57.     *subHeap = carrying;
  58.   }
  59.  
  60. template< class Element >
  61. void Heap< Element >::Remove( LinkType& toRemove )
  62.   {
  63.     Assert( toRemove.heap == this );
  64.     Assert( nodeCount > 0 );
  65.     
  66.     LinkType *spare( &RemoveLast() );
  67.     
  68.     if ( spare != &toRemove )
  69.       {
  70.         LinkType **subHeap = ⊤
  71.         spare->path = toRemove.path;
  72.         SinkNode( subHeap, spare );
  73.     
  74.         Assert( *subHeap == &toRemove );
  75.         Assert( spare->path == toRemove.path );
  76.     
  77.         *subHeap = spare;
  78.         toRemove.SwapWith( *spare );
  79.         Percolate( subHeap );
  80.       }
  81.     
  82.     toRemove.heap = 0;
  83.     Assert( toRemove.children[0] == 0 );
  84.     Assert( toRemove.children[1] == 0 );
  85.   }
  86.  
  87.  
  88. template< class Element >
  89. HeapLink<Element>** Heap< Element >::SubHeap( uint32 path )
  90.   {
  91.     Assert( path <= nodeCount );
  92.     Assert( path >= 1 );
  93.     
  94.     LinkType **subHeap = ⊤
  95.     uint32 remainingPath = path;
  96.     
  97.     while ( remainingPath > 1 )
  98.       {
  99.         Assert( *subHeap != 0 );
  100.         subHeap = &(*subHeap)->children[ remainingPath % 2 ];
  101.         remainingPath /= 2;
  102.       }
  103.     
  104.     Assert( *subHeap != 0 );
  105.     Assert( (*subHeap)->path == path );
  106.     return subHeap;
  107.   }
  108.  
  109. template< class Element >
  110. HeapLink<Element>& Heap< Element >::RemoveLast()
  111.   {
  112.     Assert( nodeCount > 0 );
  113.     LinkType **subHeap = SubHeap( nodeCount );
  114.     LinkType& removed = **subHeap;
  115.     *subHeap = 0;
  116.  
  117.     Assert( removed.children[0] == 0 );
  118.     Assert( removed.children[1] == 0 );
  119.     Assert( removed.heap == this );
  120.     Assert( removed.path == nodeCount );
  121.     removed.path = 0;
  122.     nodeCount--;
  123.     
  124.     return removed;
  125.   }
  126.  
  127. template< class Element >
  128. void Heap< Element >::SinkNode( LinkType**& subHeap,
  129.                                           LinkType*& carrying )
  130.   {
  131.     Assert( subHeap != 0 );
  132.     Assert( carrying != 0 );
  133.     
  134.     uint32 path = carrying->path;
  135.     
  136.     while( path > 1 )
  137.       {
  138.         Assert( *subHeap != 0 );
  139.         
  140.         if ( **subHeap > *carrying )
  141.           {
  142.             (*subHeap)->SwapWith( *carrying );
  143.             Swap( *subHeap, carrying );
  144.           }
  145.         
  146.         Assert( path > 1 );
  147.         subHeap = &(*subHeap)->children[ path % 2 ];
  148.         path /= 2;
  149.       }
  150.  
  151.     Assert( path == 1 );
  152.   }
  153.  
  154. template< class Element >
  155. void Heap< Element >::Percolate( LinkType** subHeap )
  156.   {
  157.     LinkType& dropping( **subHeap );
  158.     
  159.     while( true )
  160.       {
  161.         Assert( *subHeap == &dropping );
  162.         
  163.         LinkType *left = dropping.children[0];
  164.         LinkType *right = dropping.children[1];
  165.         
  166.         if ( left == 0 )
  167.           {
  168.             Assert( right == 0 );
  169.             break;
  170.           }
  171.         
  172.         if ( dropping > *left && ( right == 0 || *left <= *right ) )
  173.           {
  174.             dropping.SwapWith( *left );
  175.             Swap( *subHeap, left->children[0] );
  176.             
  177.             Assert( left->children[0] == &dropping );
  178.             Assert( *subHeap == left );
  179.             
  180.             subHeap = &left->children[0];
  181.             continue;
  182.           }
  183.         
  184.         if ( right == 0 )
  185.             break;
  186.         
  187.         if ( dropping > *right )
  188.           {
  189.             dropping.SwapWith( *right );
  190.             Swap( *subHeap, right->children[1] );
  191.             
  192.             Assert( right->children[1] == &dropping );
  193.             Assert( *subHeap == right );
  194.  
  195.             subHeap = &right->children[1];
  196.             continue;
  197.           }
  198.         
  199.         break;
  200.       }
  201.   }
  202.  
  203. template< class Element >
  204. void Heap< Element >::Validate( LinkType& node, uint32 level ) const
  205.   {
  206.     Assert( node.path > 0 );
  207.     Assert( node.path <= nodeCount );
  208.     Assert( node.heap == this );
  209.     Assert( !node.Null() );
  210.     
  211.     uint32 topBit = 1L << level;
  212.  
  213.     Assert( (node.path & topBit) != 0 );
  214.     Assert( node.path <= ( 2*topBit - 1) );
  215.  
  216.     if ( level == 31 )
  217.       {
  218.         Assert( node.children[0] == 0 );
  219.         Assert( node.children[1] == 0 );
  220.         return;
  221.       }
  222.     
  223.     uint32 rightChild = node.path | (topBit << 1);
  224.     uint32 leftChild = rightChild & ~topBit;
  225.     
  226.     if ( node.children[0] == 0 )
  227.       {
  228.         Assert( leftChild > nodeCount );
  229.       }
  230.      else
  231.       {
  232.         Assert( leftChild <= nodeCount );
  233.         Assert( node.children[0]->path == leftChild );
  234.         Assert( node <= *node.children[0] );
  235.         Validate( *node.children[0], level+1 );
  236.       }
  237.     
  238.     if ( node.children[1] == 0 )
  239.       {
  240.         Assert( rightChild > nodeCount );
  241.       }
  242.      else
  243.       {
  244.         Assert( rightChild <= nodeCount );
  245.         Assert( node.children[1]->path == rightChild );
  246.         Assert( node <= *node.children[1] );
  247.         Validate( *node.children[1], level+1 );
  248.       }
  249.   }
  250.  
  251. template< class Element >
  252. void Heap< Element >::Validate() const
  253.   {
  254.     Assert( below != 0 );
  255.     
  256.     if ( nodeCount == 0 )
  257.       {
  258.         Assert( top == 0 );
  259.       }
  260.      else
  261.       {
  262.         Assert( top != 0 );
  263.         Assert( top->path == 1 );
  264.         Validate( *top, 0 );
  265.       }
  266.   }
  267.